翻訳と辞書 Words near each other ・ Lindstedt (Gardelegen) ・ Lindston Loch, South Ayrshire ・ Lindstradt air rifle ・ Lindstrand Balloons ・ Lindstrom (disambiguation) ・ Lindstrom Field ・ Lindstrom House ・ Lindstrom Peninsula ・ Lindstrom Ridge ・ Lindstrom, Minnesota ・ Lindström ・ Lindström (company) ・ Lindström motocross ・ Lindström quantifier ・ Lindström's theorem ・ Lindström–Gessel–Viennot lemma ・ Lindstrøm & Prins Thomas ・ Lindstrøm Peak ・ Lindswell Kwok ・ Lindsy McLean ・ Lindt & Sprüngli ・ Lindt (disambiguation) ・ Lindtmayer ・ Lindtneria ・ Lindtorf ・ Lindtveit ・ Lindu ・ Linduan rousette ・ Lindula ・ Lindum Colonia Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Lindström–Gessel–Viennot lemma ： ウィキペディア英語版 Lindström–Gessel–Viennot lemma In mathematics, the Lindström–Gessel–Viennot lemma provides a way to count the number of tuples of non-intersecting lattice paths. == Statement == Let ''G'' be a locally finite directed acyclic graph. This means that each vertex has finite degree, and that ''G'' contains no directed cycles. Consider base vertices $A\; =\; \backslash$ and destination vertices $B\; =\; \backslash$, and also assign a weight $\backslash omega\_$ to each directed edge ''e''. These edge weights are assumed to belong to some commutative ring. For each directed path ''P'' between two vertices, let $\backslash omega(P)$ be the product of the weights of the edges of the path. For any two vertices ''a'' and ''b'', write ''e''(''a'',''b'') for the sum $e(a,b)\; =\; \backslash sum\_\; \backslash omega(P)$ over all paths from ''a'' to ''b''. This is well-defined if between any two points there are only finitely many paths; but even in the general case, this can be well-defined under some circumstances (such as all edge weights being pairwise distinct formal indeterminates, and $e(a,b)$ being regarded as a formal power series). If one assigns the weight 1 to each edge, then ''e''(''a'',''b'') counts the number of paths from ''a'' to ''b''. With this setup, write :. An ''n''-tuple of non-intersecting paths from ''A'' to ''B'' means an ''n''-tuple (''P''1, ..., ''P''''n'') of paths in ''G'' with the following properties: * There exists a permutation $\backslash sigma$ of $\backslash left\backslash$ such that, for every ''i'', the path ''P''''i'' is a path from $a\_i$ to $b\_$. * Whenever $i\; \backslash neq\; j$, the paths ''P''''i'' and ''P''''j'' have no two vertices in common (not even endpoints). Given such an ''n''-tuple (''P''1, ..., ''P''''n''), we denote by $\backslash sigma(P)$ the permutation of $\backslash sigma$ from the first condition. The Lindström–Gessel–Viennot lemma then states that the determinant of ''M'' is the signed sum over all ''n''-tuples ''P'' = (''P''1, ..., ''P''''n'') of ''non-intersecting'' paths from ''A'' to ''B'': :$\backslash det(M)\; =\; \backslash sum\_\; \backslash mathrm(\backslash sigma(P))\; \backslash prod\_^n\; \backslash omega(P\_i).$ That is, the determinant of ''M'' counts the weights of all ''n''-tuples of non-intersecting paths starting at ''A'' and ending at ''B'', each affected with the sign of the corresponding permutation of $(1,2,\backslash ldots,n)$, given by $P\_i$ taking $a\_i$ to $b\_$. In particular, if the only permutation possible is the identity (i.e., every ''n''-tuple of non-intersecting paths from ''A'' to ''B'' takes ''a''''i'' to ''b''''i'' for each ''i'') and we take the weights to be 1, then det(''M'') is exactly the number of non-intersecting ''n''-tuples of paths starting at ''A'' and ending at ''B''. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Lindström–Gessel–Viennot lemma」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.